package com.xj.datastructure.sort;

/**
 * author: xiajun
 * Date: 2014-07-19
 * Time: 15-17-00
 * 合并排序:是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 */
public class MergeSort {
    public static void main(String[] args) {
        int a[]={2,4,6,43};
        int b[]={5,9,10,42};
        MergeSort sort=new MergeSort();
        int []c=sort.sort(a,b);
        for (int i = 0; i < c.length; i++) {
            System.out.println(c[i]);
        }
    }

    public int[] sort(int[] a, int[] b) {
        int[] c = new int[a.length + b.length];
        int i = 0, j = 0,k=0;
        boolean isok = true;
        while (isok) {
            if (a[i] <= b[j]) {
                c[k]=a[i];
                i++;
            }else{
                c[k]=b[j];
                j++;
            }
            k++;

            if(i>=a.length||j>=b.length){
                if(j<b.length){
                    System.arraycopy(b,j,c,k,b.length-j);
                }
                if(i<a.length){
                    System.arraycopy(a,i,c,k,a.length-i);
                }
                isok=false;
            }
        }
        return c;
    }
}
